package com.wc.算法提高课.E第五章_数学知识.同余.最幸运的数字;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

/**
 * @Author congge
 * @Date 2024/10/9 15:23
 * @description https://acwing.com/problem/content/204/
 */
public class Main {
    /**
     * 背景：<p>
     * 欧拉函数 + 快速幂 + 龟速乘<p>
     * 欧拉函数：a^phi[c] = 1 (mod c), gcd(a, c) == 1
     * 思路：<p>
     * 8...8 = 8 * 1...1 = 8 * 9...9 / 9 = 8 * (10^x - 1) / 9, 有 x 个 8<p>
     * 求 8 * (10^x - 1) / 9 % L == 0 中最小的 x<p>
     * => 8 * (10^x - 1) % 9L == 0 <p>
     * => (10^x - 1) % 9L / gcd(L, 8) == 0<p>
     * 解释上述, gcd(9L, 8) = gcd(L, 8) = d, 为什么不是 8 / d * (10^x - 1) % 9L / d == 0呢, 因为 gcd(8 / d, L / d) == 1,那么只有(10^x - 1) 里面有 9L / d 的因子, 所以可以直接转化<p>
     * => 10^x - 1 = 0 (mod (9L / d)) <p>
     * => 10^x = 1 (mod (9L / d)) <p>
     * 根据欧拉函数定理, 可以推出只有 10 与 9L / d互质, 可以求出一个x = phi[9L / d] 的值<p>
     * 但是需要求出最小的 x, 那就相当于求出 phi的约数中的最小值x 满足 10 ^ x mod 9L / d == 1求出 xmin<p>
     * 证明上述<p>
     * 反证法<p>
     * 假设 phi = qx + r(0 < r < x),x不是phi的最小约数<p>
     * 10^x = 1(mod C)<p>
     * 10^(qx + r) = 1 (mod C), x是phi的约数, 所以 10^r = 1(mod C)=> r < x, 矛盾了<p>
     */
    static FastReader sc = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);
    static int N = (int) 1e6;
    static int[] primes = new int[N];
    static boolean[] st = new boolean[N];
    static int cnt = 0;

    public static void main(String[] args) {
        int T = 1;
        ola();
        while (true) {
            long L = sc.nextLong();
            if (L == 0) break;
            long d = gcd(L, 8);
            long C = 9 * L / d;
            long res = (long) 1e18;
            if (gcd(C, 10) != 1) res = 0;
            long phi = getEular(C);
            for (long i = 1; i <= phi / i; i++) {
                if (phi % i == 0) {
                    if (qmi(10, i, C) == 1) res = Math.min(res, i);
                    if (qmi(10, phi / i, C) == 1) res = Math.min(res, phi / i);
                }
            }
            out.printf("Case %d: %d\n", T++, res);
        }
        out.flush();
    }

    static void ola() {
        st[0] = st[1] = true;
        for (int i = 2; i < N; i++) {
            if (!st[i]) primes[cnt++] = i;
            for (int j = 0; primes[j] <= (N - 1) / i; j++) {
                st[i * primes[j]] = true;
                if (i % primes[j] == 0) break;
            }
        }
    }

    static long qmi(long a, long b, long p) {
        long res = 1;
        while (b > 0) {
            if ((b & 1) == 1) res = qmul(res, a, p);
            a = qmul(a, a, p);
            b >>= 1;
        }
        return res;
    }

    static long qmul(long a, long b, long p) {
        long res = 0;
        while (b > 0) {
            if ((b & 1) == 1) res = (res + a) % p;
            a = (a + a) % p;
            b >>= 1;
        }
        return res;
    }

    static long getEular(long C) {
        long res = C;
        for (int i = 0; primes[i] <= C && i < cnt; i++) {
            int p = primes[i];
            if (C % p == 0) {
                while (C % p == 0) C /= p;
                res = res / p * (p - 1);
            }
        }
        if (C > 1) res = res / C * (C - 1);
        return res;
    }

    static long gcd(long a, long b) {
        return b > 0 ? gcd(b, a % b) : a;
    }
}

class FastReader {
    StringTokenizer st;
    BufferedReader br;

    FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    String nextLine() {
        String s = "";
        try {
            s = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return s;
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    // 是否由下一个
    boolean hasNext() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = br.readLine();
                if (line == null)
                    return false;
                st = new StringTokenizer(line);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return true;
    }
}